### Reproducible builds are (not) sufficient

### О пользе reproducible packages

[Воссоздаваемые сборки](https://reproducible-builds.org) это идея, в соответствии с которой автор дистрибутива обязан предоставить все настройки, параметры среды и прочие используемые в процессе сборки из исходных кодов переменные, необходимые для воссоздания полностью идентичного бинарого пакета на машине конечного пользователя.

На момент написания заметки, [94%](https://tests.reproducible-builds.org/debian/reproducible.html) из 24821 пакетов базовой поставки Debian являются воссоздаваемыми. Однако, многие задаются вопросом: «Действительно ли факт наличия воссоздаваемых сборок сам по себе может обеспечить какую-то дополнительную степень надёжности, или же мы всего лишь ловко подменяем доверие к авторам дистрибутива доверием к другим людям, на словах заявляющим, что проверили работу авторов дистрибутива?».

Давайте разберёмся.

### В чём дело?

Инфраструктура свободного ПО отличается очень высокими требованиями к прозрачности, с целью максимально исключить возможность выполнения поставляемой программой каких-либо недокументированных действий. Во-первых, для включения в дистрибутив [необходимо](https://www.debian.org/doc/debian-policy/#the-debian-free-software-guidelines) наличия в свободном доступе полных исходных кодов собираемого программного обеспечения, для возможности независимого аудита любой части программы кем угодно.

Это требование гарантирует, что любую нежелательную инструкцию теоретически можно обнаружить до того, как она будет непосредственно исполнена процессором.

Во-вторых, обязательна юридическая возможность распространения как оригинальной, так и изменённой версии программы, таким образом гарантируется, что автор дистрибутива сможет легально исключить нежелательную инструкцию самостоятельно, не дожидаясь реакции основного разработчика, если такая будет найдена в результате аудита.

Эти правила, безусловно, хороши, однако ни одно из них не позволяет удостовериться, что автор дистрибутива не имеет возможности добавить отсутствующую в исходном коде нежелательную инструкцию в итоговую поставку пакета. Следовательно, в конечном итоге, пользователь обязан доверять сборщику дистрибутива, без возможности проверить его работу. Для того чтобы исключить эту дыру, и была придумана концепция воспроизводимых сборок.

### Что не так?

Аналогично утверждению, будто бы «никто из обывателей не читает исходные коды, следовательно, их наличие в открытом доступе не имеет смысла», есть соблазн сказать, что поскольку процедура полного побитового воспроизведения дистрибутива на потребительском железе абсурдно трудоёмка, никто, кроме подготовленых специалистов, не в состоянии её провести, а значит, воспроизводимость пакетов даёт степень надежности немногим большую, чем само наличие исходных кодов, так как пользователи в любом случае будут должны доверять заявлениям специалистов.

Однако, для обеспечения почти 100% уверенности в добросовестности собрки, не обязательно каждому проверять её всю. Можно посчитать точные вероятности для каждого из случаев, для того и изобрели математику.

### Посчитаем?

Всего в базовой поставке debian stable [24821](https://packages.debian.org/stable/allpackages?format=txt.gz) пакет. Согласно официальной статистике пакета popularity-contest, хотя бы раз за эту неделю последний debian stretch запускали по меньшей мере (функция участия в анонимной статистике должна быть [эксплицитно включена](http://popcon.debian.org/README) пользователем при установке) на [62909](http://popcon.debian.org) машинах.

![](https://notabug.org/fullFeaturedUnicorn/public/raw/master/res/Screenshot%20from%202017-10-15%2022-40-28.png)

Предположим, пользователь не использует ни один из 5,2% невоспроизводимых пакетов, а использует оставшиеся 23347, предположим так же, что один из задекларированных воспроизводимыми пакетов собран неправильно, к примеру, содержит в себе не запланированный разработчиком оригинального ПО [бэкдор](https://en.wikipedia.org/wiki/Backdoor_(computing)).

Значит, по [формуле Бернулли](https://ru.wikipedia.org/wiki/%D0%A4%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B0_%D0%91%D0%B5%D1%80%D0%BD%D1%83%D0%BB%D0%BB%D0%B8) чистая вероятность для одного человека при ручной проверке трёх случайных пакетов наткнуться на неправильно собранный:

Количество способов выбрать 3 элемента из 23347:
```
>>> math.factorial(23347)/(math.factorial(3)*math.factorial(23347-3)) = 2120733967065
```
Количество способов выбрать 3 элемента, 1 из которых искомый (по сути, количество сопосбов, отобрав один, выбрать 2 оставшихся):
```
>>> math.factorial(23347-1)/(math.factorial(2)*math.factorial((23347-1)-2)) = 272506185
```
Вероятность, что эти события пересекутся:
```
>>> 272506185/2120733967065 = 0.00012849616653103182 ≈ 0.013%

```
Не много. Предположим, что таким образом пакеты проверило 100 человек. Тогда вероятность того, что хотя бы один из них найдет неправильно собранный пакет будет выражаться как классическое произведение вероятностей:

```
>>> 1-pow((1-0.00012849616653103182),100) = 0.012768227894149664 ≈ 1.28%
```

Для наглядности, можно построить график зависимости количества проверивших как минимум 3 пакета от вероятности найти неправильно собранный пакет:

```
df <- as.data.frame(seq(1,62909))
df$power <- 1-0.9998714928250161^df$`seq(1, 62909)`
plot(df,type="l")
grid(10, 10, lwd = 1)
```

![](https://notabug.org/fullFeaturedUnicorn/public/raw/master/res/Rplot01.png)

Как видно из графика, примерно на отметке в 30000 вовлеченных пользователей, вероятность, что никто не обнаружит пакет с ошибкой приближается к нулю.

### А если пакетов проверялось больше?

Это тоже можно проверить. Так мы составим таблицу вероятностей найти битый пакет в зависимости от количества проверенных одним пользователем случайных пакетов:

```
import math

x = 23347
for i in range (3,x):
    a = math.factorial(23347)//math.factorial(i)*math.factorial(23347-i)
    b = math.factorial(23346)//math.factorial(i-1)*math.factorial(23346-(i-1))
    print(b/a)
```

График будет выглядеть как прямая линия от нулевой, до 100% вероятности:

![](https://notabug.org/fullFeaturedUnicorn/public/raw/master/res/Rplot02.png)

Неплохо было бы вышеприведенные визуализации как-то совместить, для того чтобы получить исчерпывающую картину. Поскольку вероятности найти битый пакет совместными усилиями рассчитываются как степень от вероятности найти такой пакет в одиночку, легко составить сводную таблицу:

```
# R

library(readr)
txt <- read_csv("~/path/to/file.txt", col_names = FALSE)
for (i in seq(2,62909)){txt[[i]] <- 1-(1-txt$X1)^i}
```

И построить красивый сводный график:

```
persp(as.matrix(txt))
```

Это, однако, потребует огромного количества памяти, и не имеет большого смысла, так как все значения выше, скажем, [1000,1000] будут находиться очень близко к единице. Есть смысл построить такой график для некоторого количества наиболее реалистичных значений.

```
for (i in seq(2,1000)){mx[[i]] <- 1-(1-mx$X1)^i}
```

Покажет вероятности найти неправильно собранный пакет от точки, где 1 человек проверил 1 случайно выбранный пакет, до точки, где 1000 человек проверило 1000 случайно выбранных пакетов.

```
install.packages("rgl")
library(rgl)
persp3d(as.matrix(txt),col="skyblue")
```

![](https://notabug.org/fullFeaturedUnicorn/public/raw/master/res/Rplot04.png)

Как можно увидеть из графика, примерная вероятность обнаружить среди кучи из 23000 пакетов один неправильно собранный приближается к высоким значениям только в случаях, когда примерно 1000 людей готовы проверить каждый по 1000 случайных пакетов. График же с пределом в точке: 100 людей, по 100 пакетов, выглядит вот так:

![](https://notabug.org/fullFeaturedUnicorn/public/raw/master/res/Rplot05.png)

Я не буду делать никаких выводов. Насколько реалистичны эти цифры, насколько обосновано предполагать, что из всей аудитории пользователей Debian 1000 людей озаботится проверкой всех своих любимых пакетов – не знаю. В любом случае, факт возможности получить полную информацию об окружении в процессе сборки это большой шаг навстречу пользователю, важность которого трудно переоценить.

Однако, полностью исключить доверие к централизованному предоставителю услуг, и отдать контроль над каждым аспектом работы системы в руки пользователя, всё ещё не получилось. Хотя из описания практики может показаться, что именно с приходом reproducible packages в этом вопросе была заштукатурена последняя дыра.

### So how to verify by hand if package is reproducible

I'll go through entire process. It's up to you to decide if it's hard or not. First of all, we need of course, clean Debian installation in a [VM](https://wiki.debian.org/QEMU), or on a real hardware, package groups `build-essential`, `fakeroot`, `devscripts` and a bit of patience. Also, it's very handy to download full [official structured list](https://reproducible.debian.net/reproducible.json) of packages, even though recommended way to check out package status is to use simple python [script](https://anonscm.debian.org/cgit/reproducible/misc.git/tree/unreproducible-installed).

Let's start with something stupidly simple, so no package-specific bugs will interfere. Again, here we talk about VERY sensitive subject, where absolute bitwise precision matters. I choose my favorite piece of software ever – [tmux](http://man.openbsd.org/OpenBSD-current/man1/tmux.1) terminal multiplexer, it's lightweight and has very high code quality. I've just made sure it marked as reproducible by debian project.

```
{
        "architecture": "amd64",
        "build_date": "2017-06-16 00:13",
        "package": "tmux",
        "status": "reproducible",
        "suite": "stretch",
        "version": "2.3-4"
}
```

**Step 1**. Obtain source. Navigate to and empty directory and exec `apt source tmux`. Easy-peasy.

**Step 2**. Obtain .buildinfo file with dependencies, environment variables and everything needed to reproduce exactly the same build. Navigate to continous integration system [page](https://tests.reproducible-builds.org/debian/reproducible.html) and search for needed package. [Here](https://tests.reproducible-builds.org/debian/rb-pkg/stretch/amd64/tmux.html) it is. Notice checksums at the beginning. It is [essential](https://en.wikipedia.org/wiki/Checksum) to check package integrity for anyone unfamiliar with that shit.

```
Checksums-Md5:
 70686e3b722bc94d48910d6a93914fa6 982704 tmux-dbgsym_2.3-4_amd64.deb
 bdc7e6789cd735bf0bc843f775a69b71 264862 tmux_2.3-4_amd64.deb
Checksums-Sha1:
 f0b0b76faae4862c71e1dc5e6b0ed6c799cde561 982704 tmux-dbgsym_2.3-4_amd64.deb
 bcadd30228602c50f49e84c255c7167b592251cf 264862 tmux_2.3-4_amd64.deb
Checksums-Sha256:
 53d956fa9fbf4a49fb1cfe1d3c49c405a4ed7cfd00a1412b32be0e8a4af37c0f 982704 tmux-dbgsym_2.3-4_amd64.deb
 9166d818afedc4e571d0cbe5bab66c940837cd9c238d1de6d5369c64a692e707 264862 tmux_2.3-4_amd64.deb
```

**Step 3**. Install missing build dependecies using `sudo apt build-dep tmux`. Without this packages build likely will fail bacause of missing header files.

```
he following NEW packages will be installed:
  libevent-core-2.0-5 libevent-dev libevent-extra-2.0-5 libevent-openssl-2.0-5
  libevent-pthreads-2.0-5 libncurses5-dev libtinfo-dev libutempter-dev
  libutempter0 pkg-config
0 upgraded, 10 newly installed, 0 to remove and 0 not upgraded.
Need to get 874 kB of archives.
After this operation, 3,756 kB of additional disk space will be used.
Do you want to continue? [Y/n]
```

**Step 4**. Carefully check out anything mentioned in .buildinfo file and make sure it set up exactly the same way on your installation. For example, in case of tmux we need to verify 4 environment variables. Let's print what we got on the host system:

```
$ printenv DEB_BUILD_OPTIONS LANG LC_ALL SOURCE_DATE_EPOCH
en_US.UTF-8
```

It doesn't match. We need to set up this variables. This can be done using command `export` (don't worry, every mentioned change is temporary, after reboot they'll all be gone if we'll mess up).

```
$ export DEB_BUILD_OPTIONS="buildinfo=+all parallel=15" LANG="C" LC_ALL="C" SOURCE_DATE_EPOCH="1477219712"
```

Check out again

```
$ printenv DEB_BUILD_OPTIONS LANG LC_ALL SOURCE_DATE_EPOCH
buildinfo=+all parallel=15
C
C
1477219712
```

Exactly! Seems like we're ready to build a package.

**Step 5**. Building. Navigate to directory with name formatted like "packagename-packageversion", in my case it's `tmux-2.3` and run `debuild -i -us -uc -b` as mentioned [here](https://wiki.debian.org/BuildingTutorial). Wait for the compilation, notice at the end of the process string which tells you where to fing compiled package. Like this:

```
dpkg-deb: building package 'tmux' in '../tmux_2.3-4_amd64.deb'.
```

**Step 6**. Verify. Invoke `sha256sum ../tmux_2.3-4_amd64.deb` and compare result to the one mentioned in buildinfo. If you've got the same numbers, congratulations, the package is reproducible! Here's what i've got:

![](https://notabug.org/fullFeaturedUnicorn/public/raw/master/res/Screenshot%20from%202017-10-16%2009-34-54.png)

Party fucking hard lol. Only 999 packages to go.